package code;


public class MaximumPathSum {
	static public class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x){
			val=x;
		}
	}
	
	private int max;
	
	public int dfs(TreeNode p){
		if(p.left==null && p.right==null){
			if(max<p.val)
				max=p.val;
			return p.val;
		}
		boolean hasLeftChild=false;
		boolean hasRightChild=false;
		int maxLeft=0;
		int maxRight=0;
		/*
		 * ����������Ľ����
		 */
		if(p.left!=null){
			maxLeft=dfs(p.left)+p.val;
			if(max<maxLeft)
				max=maxLeft;
			hasLeftChild=true;
		}
		/*
		 * ����������Ľ����
		 */
		if(p.right!=null){
			maxRight=dfs(p.right)+p.val;
			if(max<maxRight)
				max=maxRight;
			hasRightChild=true;
		}
		/*
		 * �����ڵ��ֵ���
		 */
		if(max<p.val)	max=p.val;
		/*
		 * ������+��������ֵ���
		 */
		if(max<maxLeft+maxRight-p.val)
			max=maxLeft+maxRight-p.val;
		int ret=p.val;
		if(!hasLeftChild){
			if(ret<maxRight)
				ret=maxRight;
		}
		if(!hasRightChild){
			if(ret<maxLeft)
				ret=maxLeft;
		}
		if(hasRightChild && hasLeftChild){
			if(ret<maxRight)
				ret=maxRight;
			if(ret<maxLeft)
				ret=maxLeft;
		}
		return ret;
	}
    public int maxPathSum(TreeNode root) {
    	
    	if(root==null)	return 0;
    	max=Integer.MIN_VALUE;
        dfs(root);
        return max;
    }
    
    public static void main(String[] args){
    	TreeNode root=new TreeNode(-2);
    	TreeNode a=new TreeNode(-1);
    	TreeNode b=new TreeNode(3);
    	TreeNode c=new TreeNode(-5);
    	TreeNode d=new TreeNode(1);
    	root.left=a;
//    	root.right=b;
//    	a.left=c;
//    	c.left=d;
    	MaximumPathSum mps=new MaximumPathSum();
    	System.out.println(mps.maxPathSum(root));
    }
}
